package com.practice.shua1;

/**
 * 【leetcode 1143 最长公共子序列】（TODO：一个作行一个左列的对应模型）
 * 【题目】：
 * 给定两个字符串text1和text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
 * 一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
 * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
 * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
 * 【示例1】：
 * 输入：text1 = "abcde", text2 = "ace"
 * 输出：3
 * 解释：最长公共子序列是 "ace" ，它的长度为 3 。
 * 【示例2】：
 * 输入：text1 = "abc", text2 = "abc"
 * 输出：3
 * 解释：最长公共子序列是 "abc" ，它的长度为 3 。
 * 【示例3】：
 * 输入：text1 = "abc", text2 = "def"
 * 输出：0
 * 解释：两个字符串没有公共子序列，返回 0 。
 * 【提示】：
 * 1 <= text1.length, text2.length <= 1000
 * text1 和 text2 仅由小写英文字符组成。
 *
 * @author lineng
 * @create 2021-05-01 17:25
 */
public class code_03_LongestCommonSubsequence {

    // https://leetcode-cn.com/problems/longest-common-subsequence/
    // AC 通过
    public static int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) {
            return 0;
        }
        return myDp(text1.toCharArray(), text2.toCharArray());
    }

    // chs1[0...i-1]和chs2[0...j-1]已经做了决定
    // 轮到chs1[i]和chs2[j]做决定
    // dp[i][j]表示
    // 求chs1[0...i]与chs2[0...j]的最长公共子序列
    // int[][] dp = new int[chs1.length][chs2.length]，最终返回dp[chs1.length-1][chs2.length-1]
    // 求dp[i][j]时：
    // 如果 chs1[i]!=chs2[j] ====> dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]
    // 如果 chs1[i]==chs2[j] ===> dp[i][j] = dp[i-1][j-1] + 1
    public static int myDp(char[] chs1, char[] chs2) {
        int N = chs1.length;
        int M = chs2.length;
        int[][] dp = new int[N][M];
        // 填好第0行，第0行中一旦发现chs2[i]==chs1[0], 当前位置和后面位置都为1
        int cloIndex = -1;
        for (int i = 0; i < M; i++) {
            if (chs1[0] == chs2[i]) {
                cloIndex = i;
                break;
            }
        }
        if (cloIndex >= 0) {
            for (int i = cloIndex; i < M; i++) {
                dp[0][i] = 1;
            }
        }
        // 填好第0列，第0列中一旦发现chs1[i]==chs2[0], 当前位置和下面位置都为1
        int rowIndex = -1;
        for (int i = 0; i < N; i++) {
            if (chs2[0] == chs1[i]) {
                rowIndex = i;
            }
        }
        if (rowIndex >= 0) {
            for (int i = rowIndex; i < N; i++) {
                dp[i][0] = 1;
            }
        }
        // 填好普遍位置dp[i][j]
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                // 枚举公共子序列是否以chs1[i]或者chs2[j]结尾
                // 可以有如下几种选择（每种都可以选，只是最后一种有条件）：
                // (1) 子序列既不以chs1[i]结尾也不以chs2[j]结尾 dp[i][j] = dp[i-1][j-1]
                // (2) 子序列以chs1[i]结尾，但是不以chs2[j]结尾 dp[i][j] = dp[i][j-1];
                // (3) 子序列不以chs1[i]结尾，但是以chs2[j]结尾 dp[i][j] = dp[i-1][j];
                // (4) 当chs1[i] == chs2[j]时，子序列可以即以chs1[i]结尾也以chs2[j]结尾，dp[i][j] = dp[i-1][j-1]+1

                dp[i][j] = Math.max(Math.max(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]);
                if (chs1[i] == chs2[j]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[N - 1][M - 1];
    }

}
